The present invention relates to data networking, and more particularly to path computation in certain types of situations.
MPLS (Multi-Protocol Label Switching) Traffic Engineering has been developed to meet data networking requirements such as guaranteed available bandwidth. MPLS Traffic Engineering exploits modem label switching techniques to build guaranteed bandwidth end-to-end tunnels through an IP/MPLS network of label switched routers (LSRs). These tunnels are a type of label switched path (LSP) and thus are generally referred to as MPLS Traffic Engineering LSPs.
Establishment of an MPLS Traffic Engineering LSP from a head-end to a tail-end involves computation of a path for a network of LSRs. Optimally, the computed path is the “shortest” path, as measured in some metric, that satisfies all of the relevant constraints such as e.g., required bandwidth, affinities, etc. Computation of the path generally requires knowledge of network topology and available resources on nodes between the head-end and tail-end.
It is desirable to establish MPLS Traffic Engineering LSPs across the borders of Autonomous Systems and areas. The term “Autonomous System” generally refers to a group of routers within a network that are subject to a common authority and use the same intradomain routing protocol. An “area” is a collection of routers that share full network topology information with each other but not routers in other areas. To improve routing scalability, the service provider may divide Autonomous System into multiple areas.
U.S. patent application Ser. No. 10/767,574 explains techniques to compute paths of MPLS Traffic Engineering LSPs across the boundaries of areas and/or Autonomous Systems. To overcome the difficulty posed by the lack of a global view of network topology and resources, the path computation operations are distributed among multiple path computation elements (PCEs) positioned in each of the multiple Autonomous Systems or areas.
The path computation elements cooperate to establish and develop a virtual shortest path tree (VSPT) in an iterative and recursive fashion. In one virtual shortest path tree computation procedure, a requesting head-end sends its request for placement of an MPLS Traffic Engineering LSP to a local path computation element in the same Autonomous System or area. This path computation element forwards the path computation request to the path computation element in the next Autonomous System or area on the way to the requested tail-end. The path computation request is propagated from path computation element to path computation element until it reaches the path computation element in the same Autonomous System or area that contains the tail-end.
This final path computation element computes a virtual shortest path tree routed at the tail-end node and extending to the border routers that couple the local Autonomous System or area to the previous one in line back to the head-end. Once this virtual shortest path tree has been computed, information specifying it is transferred back to the previous path computation element. That path computation element extends the virtual shortest path tree to the border routers facing the next previous Autonomous System or area and transmits a specification of the extended tree to the next previous path computation element. When the virtual shortest path tree reaches the path computation element that received the original request from the head-end, that path computation element uses the received virtual shortest path tree and local network topology and resource information to compute the end-to-end path between the head-end and tail-end. The computed path information is then forwarded to the requesting head-end.
It can be seen then that this is essentially a serial computation technique even though the computations are distributed among multiple path computation elements. Each path computation element waits to receive virtual shortest path tree information from any downstream (towards tail-end) path computation elements before beginning its own computations. The computations undertaken by each path computation element may be very time consuming especially when there are multiple optimization criteria and constraints involved. Thus the accumulated computation time along the chain of path computation elements may be very large. A path computation element may in fact time out its request after not receiving requested virtual shortest path tree information for an extended period and try again, further adding to the load on processing resources.
What is needed are systems and methods for accelerating path computations employing the virtual shortest path tree technique.